Generally, digital halftoning is accomplished by either bi-tonal or multi-tonal halftoning methods. Bi-tonal halftoning is widely used in the art and is a basic digital halftoning method from which multi-tonal halftoning methods are derived. Therefore, bi-tonal digital halftoning is discussed below as a precursor to a discussion of multi-tonal halftoning.
In general, bi-tonal digital halftoning converts a continuous tone image into a halftone image consisting of a pattern of equal intensity dots. Each dot within the halftone image either exists (black) or does not exist (white), i.e., a bi-tonal image. More specifically, bi-tonal digital halftoning converts a plurality of digitized intensity values representing a continuous tone image into a plurality of halftone cells, where each halftone cell corresponds to each intensity value. Moreover, the number of dots within each halftone cell is proportional to the magnitude of each corresponding intensity value. The intensity values are typically generated by periodically sampling a continuous tone image using an optical scanner. Each intensity value represents the image intensity in an immediate area surrounding the location within the continuous tone image from which an intensity value sample was taken. Typically, each intensity value is quantized into a plurality of levels known as gray scale levels. Quantization permits each intensity value to be represented by a digital value and processed by digital circuitry into a halftone image. For instance, if the intensity value is quantized into 256 levels, i.e., a 256 level gray scale, the intensity value can be represented by an eight-bit digital word.
During bi-tonal digital halftoning, each intensity value is spatially mapped into a corresponding halftone cell. As noted above, each halftone cell typically encompasses a plurality of pixels, each having a bi-tonal value, i.e., either black or white. However, some applications require the number of intensity values to equal the number of pixels in the halftone cell, i.e., equal scanner and halftone resolutions. Generally speaking, regardless of the application, the arrangement of bi-tonal pixels within the halftone image is perceived by a viewer of the halftone image to have a gray scale intensity commensurate with the magnitude of each associated intensity value. The above described mapping process is generally known as spatial modulation.
In operation, a bi-tonal digital halftoning system compares each intensity value sample to a matrix of modulation levels and generates a halftone cell corresponding to each intensity value. Typically, this matrix has a number of elements equivalent to the number of pixels in the halftone cell. To generate the bi-tonal halftone cell, a given intensity value is compared to each modulation level in the matrix. Each pixel in the halftone cell, that corresponds to a modulation level in the modulation level matrix and is lesser in value than the intensity value, is made black; otherwise, the pixel is white. Thus, the intensity value is mapped into an area comprised of an arrangement of black and white pixels whose overall intensity is commensurate with the magnitude of the intensity value.
The arrangement of modulation levels within the modulation level matrix is generally known as dithering, more specifically, in two common forms: clustered dot dithering and dispersed dot dithering. In essence, through dithering, the modulation levels are arranged to ensure that the resultant halftone pixels that will be generated for a given cell will accurately reflect the intensity of the input intensity value associated with that cell. For a detailed discussion of dithering in bi-tonal systems, see Ulichney, Digital Halftoning, pp. 71-171 (MIT Press, .COPYRGT.1987).
The matrix comparison process, as described above, is repeated for each intensity value sampled from the original continuous tone image. As a result, the entire image is spatially modulated into a halftone image comprised of a tile-like arrangement of halftone cells each representing a different corresponding intensity value sample.
As is well known in the art, the halftoning process thus far described is useful in halftoning color images by repeating the bi-tonal process for each primary color, i.e., red, blue, and green or cyan, magenta, and yellow, and, subsequently, overlaying the resulting color halftone images with proper registration.
Multi-level halftoning is an extension of bi-tonal halftoning. As its name implies, multi-level halftoning replaces each black or white pixel in a bi-tonal halftone cell with a pixel having a value selected from a number of values available for each pixel. In essence, multi-level halftoning redistributes the intensity of a single intensity value into a plurality of intensity values within a halftone cell. Many display devices permit multi-level pixel display; multi-level halftoning takes advantage of this capability. For example, thermal printers are capable of printing dot sizes that correspond to each pixel intensity level. Additionally, cathode ray tube (CRT) displays can display various pixel intensities by altering an electron beam strength incident upon each pixel within the CRT display.
Typically, display devices are limited as to the number of levels that they can display. In contrast, sampling devices can produce many different output levels. Therefore, multi-level halftoning is used to convert a large number of output levels from a sampling device into a lesser number of levels compatible with a display device. For instance, if a display device can accurately display five levels while a scanner can provide a 256 level intensity value, a multi-level halftoning system must distribute each single 256 level value into a halftone cell, containing a plurality of five level pixels, that, when viewed, appears as the 256 level value.
To determine the appropriate level for each pixel in a multi-level halftone cell, an input intensity value is compared to a number of modulation level matrices, i.e., N-1 matrices are used to generate N levels. Generally, the comparison process is similar to that used in bi-tonal halftoning except the comparison process is repeated N-1 times for N-1 matrices. As in bi-tonal halftoning, each matrix contains, as matrix elements, a number of different modulation levels. The number of matrix elements is equivalent to the number of pixels in the halftone cell. The output of each comparison is a digital bit, i.e., a signal having a value of either a logical "1" or logical "0". The output bit value indicates whether the intensity value is greater than the modulation level, i.e., logical "1" or less than the modulation level, i.e., logical "0". Each output bit is stored in an intermediate matrix. Thus, a set of N intermediate matrices containing digital bits is generated. An encoder combines the elements of the intermediate matrices to generate the pixel values for a halftone cell.
For example, an intensity value may be quantized by an 8-bit scanner to have a value between 0 and 255. The intensity value is compared to four matrices. Each matrix contains modulation levels arranged in a 4-by-4 matrix having various modulation levels ranging from 0 to 255. Comparing each modulation level in each matrix to the intensity value results in four intermediate matrices containing digital values. The elements of each intermediate matrix are valued at a logical "1" whenever the intensity value is larger than the corresponding modulation level; otherwise, a logical "0" is used as the matrix element. In essence, the four intermediate matrices are four bi-tonal halftone cells. The elements of each intermediate matrix having the same coordinates are combined to form a 4-bit word. Each 4-bit word is then encoded to generate a halftone output value for a pixel in the multi-level halftone cell. The resulting pixel value will range from 0 to 4, i.e., one level for each modulation level matrix with one level to signify the absence of a pixel.
As in the case of bi-tonal halftoning, the modulation levels are placed in a dither pattern within each modulation level matrix. The dither patterns used are essentially the same as those used in bi-tonal halftoning, i.e., clustered-dot dither or dispersed-dot dither.
Currently, the modulation levels in each matrix of a multi-level halftoning system are generated manually. These levels are then arranged using empirical methods to achieve a desired intensity value to halftone cell conversion. The number of modulation levels that needs to be specified is (m.times.n)(N-1), where: N is the number of desired output levels, and m and n are the dimensions in matrix elements of the modulation level matrices. In practice, the number of modulation levels that must be generated can be quite large. For example, a system having 12 output levels with 8-by-8 element matrices requires that 64 modulation levels must be specified and then properly arranged in each of 11 modulation level matrices.
Moreover, to accomplish each intensity value comparison, N-1 comparator circuits associated with N-1 modulation level matrices are necessary to produce an N-level output. Thus, a conventional multi-level halftone system requires a dedicated number of comparators and associated matrices to generate each of the output levels. Consequently, each halftoning system must be designed to accommodate a specific number of output levels to drive a specific display device. Thus, a single multi-level halftone image generating system cannot be readily altered to accommodate any number of output levels and hence is rather inflexible.
Therefore, a specific need exists in the art for apparatus that generates multi-level output values for pixels in a halftone cell in a manner which readily accommodates any number of output levels. Specifically, a need exists in the art for apparatus that generates multi-level values without using an arrangement of comparators and modulation level matrices. Additionally, a need exists in the art for apparatus that automatically generates modulation levels for each of the modulation level matrices.